home *** CD-ROM | disk | FTP | other *** search
/ MPEG Toolkit / MPEG Toolkit.iso / os2 / mpegenc / src / pbmplus / ppm / libppm3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-01  |  6.2 KB  |  263 lines
  1. /* libppm3.c - ppm utility library part 3
  2. **
  3. ** Colormap routines.
  4. **
  5. ** Copyright (C) 1989, 1991 by Jef Poskanzer.
  6. **
  7. ** Permission to use, copy, modify, and distribute this software and its
  8. ** documentation for any purpose and without fee is hereby granted, provided
  9. ** that the above copyright notice appear in all copies and that both that
  10. ** copyright notice and this permission notice appear in supporting
  11. ** documentation.  This software is provided "as is" without express or
  12. ** implied warranty.
  13. */
  14.  
  15. #include "ppm.h"
  16. #include "ppmcmap.h"
  17. #include "libppm.h"
  18.  
  19. #define HASH_SIZE 20023
  20.  
  21. #ifdef PPM_PACKCOLORS
  22. #define ppm_hashpixel(p) ( ( (int) (p) & 0x7fffffff ) % HASH_SIZE )
  23. #else /*PPM_PACKCOLORS*/
  24. #define ppm_hashpixel(p) ( ( ( (long) PPM_GETR(p) * 33023 + (long) PPM_GETG(p) * 30013 + (long) PPM_GETB(p) * 27011 ) & 0x7fffffff ) % HASH_SIZE )
  25. #endif /*PPM_PACKCOLORS*/
  26.  
  27. colorhist_vector
  28. ppm_computecolorhist( pixels, cols, rows, maxcolors, colorsP )
  29.     pixel** pixels;
  30.     int cols, rows, maxcolors;
  31.     int* colorsP;
  32.     {
  33.     colorhash_table cht;
  34.     colorhist_vector chv;
  35.  
  36.     cht = ppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP );
  37.     if ( cht == (colorhash_table) 0 )
  38.     return (colorhist_vector) 0;
  39.     chv = ppm_colorhashtocolorhist( cht, maxcolors );
  40.     ppm_freecolorhash( cht );
  41.     return chv;
  42.     }
  43.  
  44. void
  45. ppm_addtocolorhist( chv, colorsP, maxcolors, colorP, value, position )
  46.     colorhist_vector chv;
  47.     pixel* colorP;
  48.     int* colorsP;
  49.     int maxcolors, value, position;
  50.     {
  51.     int i, j;
  52.  
  53.     /* Search colorhist for the color. */
  54.     for ( i = 0; i < *colorsP; ++i )
  55.     if ( PPM_EQUAL( chv[i].color, *colorP ) )
  56.         {
  57.         /* Found it - move to new slot. */
  58.         if ( position > i )
  59.         {
  60.         for ( j = i; j < position; ++j )
  61.             chv[j] = chv[j + 1];
  62.         }
  63.         else if ( position < i )
  64.         {
  65.         for ( j = i; j > position; --j )
  66.             chv[j] = chv[j - 1];
  67.         }
  68.         chv[position].color = *colorP;
  69.         chv[position].value = value;
  70.         return;
  71.         }
  72.     if ( *colorsP < maxcolors )
  73.     {
  74.     /* Didn't find it, but there's room to add it; so do so. */
  75.     for ( i = *colorsP; i > position; --i )
  76.         chv[i] = chv[i - 1];
  77.     chv[position].color = *colorP;
  78.     chv[position].value = value;
  79.     ++(*colorsP);
  80.     }
  81.     }
  82.  
  83. colorhash_table
  84. ppm_computecolorhash( pixels, cols, rows, maxcolors, colorsP )
  85.     pixel** pixels;
  86.     int cols, rows, maxcolors;
  87.     int* colorsP;
  88.     {
  89.     colorhash_table cht;
  90.     register pixel* pP;
  91.     colorhist_list chl;
  92.     int col, row, hash;
  93.  
  94.     cht = ppm_alloccolorhash( );
  95.     *colorsP = 0;
  96.  
  97.     /* Go through the entire image, building a hash table of colors. */
  98.     for ( row = 0; row < rows; ++row )
  99.     for ( col = 0, pP = pixels[row]; col < cols; ++col, ++pP )
  100.         {
  101.         hash = ppm_hashpixel( *pP );
  102.         for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  103.         if ( PPM_EQUAL( chl->ch.color, *pP ) )
  104.             break;
  105.         if ( chl != (colorhist_list) 0 )
  106.         ++(chl->ch.value);
  107.         else
  108.         {
  109.         if ( ++(*colorsP) > maxcolors )
  110.             {
  111.             ppm_freecolorhash( cht );
  112.             return (colorhash_table) 0;
  113.             }
  114.         chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  115.         if ( chl == 0 )
  116.             pm_error( "out of memory computing hash table" );
  117.         chl->ch.color = *pP;
  118.         chl->ch.value = 1;
  119.         chl->next = cht[hash];
  120.         cht[hash] = chl;
  121.         }
  122.         }
  123.     
  124.     return cht;
  125.     }
  126.  
  127. colorhash_table
  128. ppm_alloccolorhash( )
  129.     {
  130.     colorhash_table cht;
  131.     int i;
  132.  
  133.     cht = (colorhash_table) malloc( HASH_SIZE * sizeof(colorhist_list) );
  134.     if ( cht == 0 )
  135.     pm_error( "out of memory allocating hash table" );
  136.  
  137.     for ( i = 0; i < HASH_SIZE; ++i )
  138.     cht[i] = (colorhist_list) 0;
  139.  
  140.     return cht;
  141.     }
  142.  
  143. int
  144. ppm_addtocolorhash( cht, colorP, value )
  145.     colorhash_table cht;
  146.     pixel* colorP;
  147.     int value;
  148.     {
  149.     register int hash;
  150.     register colorhist_list chl;
  151.  
  152.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  153.     if ( chl == 0 )
  154.     return -1;
  155.     hash = ppm_hashpixel( *colorP );
  156.     chl->ch.color = *colorP;
  157.     chl->ch.value = value;
  158.     chl->next = cht[hash];
  159.     cht[hash] = chl;
  160.     return 0;
  161.     }
  162.  
  163. colorhist_vector
  164. ppm_colorhashtocolorhist( cht, maxcolors )
  165.     colorhash_table cht;
  166.     int maxcolors;
  167.     {
  168.     colorhist_vector chv;
  169.     colorhist_list chl;
  170.     int i, j;
  171.  
  172.     /* Now collate the hash table into a simple colorhist array. */
  173.     chv = (colorhist_vector) malloc( maxcolors * sizeof(struct colorhist_item) );
  174.     /* (Leave room for expansion by caller.) */
  175.     if ( chv == (colorhist_vector) 0 )
  176.     pm_error( "out of memory generating histogram" );
  177.  
  178.     /* Loop through the hash table. */
  179.     j = 0;
  180.     for ( i = 0; i < HASH_SIZE; ++i )
  181.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chl->next )
  182.         {
  183.         /* Add the new entry. */
  184.         chv[j] = chl->ch;
  185.         ++j;
  186.         }
  187.  
  188.     /* All done. */
  189.     return chv;
  190.     }
  191.  
  192. colorhash_table
  193. ppm_colorhisttocolorhash( chv, colors )
  194.     colorhist_vector chv;
  195.     int colors;
  196.     {
  197.     colorhash_table cht;
  198.     int i, hash;
  199.     pixel color;
  200.     colorhist_list chl;
  201.  
  202.     cht = ppm_alloccolorhash( );
  203.  
  204.     for ( i = 0; i < colors; ++i )
  205.     {
  206.     color = chv[i].color;
  207.     hash = ppm_hashpixel( color );
  208.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  209.         if ( PPM_EQUAL( chl->ch.color, color ) )
  210.         pm_error(
  211.             "same color found twice - %d %d %d", PPM_GETR(color),
  212.             PPM_GETG(color), PPM_GETB(color) );
  213.     chl = (colorhist_list) malloc( sizeof(struct colorhist_list_item) );
  214.     if ( chl == (colorhist_list) 0 )
  215.         pm_error( "out of memory" );
  216.     chl->ch.color = color;
  217.     chl->ch.value = i;
  218.     chl->next = cht[hash];
  219.     cht[hash] = chl;
  220.     }
  221.  
  222.     return cht;
  223.     }
  224.  
  225. int
  226. ppm_lookupcolor( cht, colorP )
  227.     colorhash_table cht;
  228.     pixel* colorP;
  229.     {
  230.     int hash;
  231.     colorhist_list chl;
  232.  
  233.     hash = ppm_hashpixel( *colorP );
  234.     for ( chl = cht[hash]; chl != (colorhist_list) 0; chl = chl->next )
  235.     if ( PPM_EQUAL( chl->ch.color, *colorP ) )
  236.         return chl->ch.value;
  237.  
  238.     return -1;
  239.     }
  240.  
  241. void
  242. ppm_freecolorhist( chv )
  243.     colorhist_vector chv;
  244.     {
  245.     free( (char*) chv );
  246.     }
  247.  
  248. void
  249. ppm_freecolorhash( cht )
  250.     colorhash_table cht;
  251.     {
  252.     int i;
  253.     colorhist_list chl, chlnext;
  254.  
  255.     for ( i = 0; i < HASH_SIZE; ++i )
  256.     for ( chl = cht[i]; chl != (colorhist_list) 0; chl = chlnext )
  257.         {
  258.         chlnext = chl->next;
  259.         free( (char*) chl );
  260.         }
  261.     free( (char*) cht );
  262.     }
  263.